The invention relates generally to computer processors, and deals more particularly with a technique for predicting an address required to execute a program instruction based on one or more previous addresses used to execute previous instances of the same program instruction.
An address is required to execute some program instructions. For example, a write operation requires an address to which to write data, and a read operation requires an address from which to fetch data. A mathematical operation such as addition, subtraction, multiplication or division may require both an address from which to fetch data operands and an address to which to write the result of the mathematical operation. In some cases, the address is generated by a previous program instruction, and execution of the write, read or mathematical operation awaits generation of the address. This type of dependency is called "address generation interlock" (AGI).
The following is an example of AGI. In step one, a program instructs that an initial memory address be loaded into a first register. Then, in step two, the program instructs that the contents of the memory address stored in the first register be added to the contents of a second register. Then, in step three, the program instructs that the address stored in the first register be changed based on some formula or other criteria. Then, the program increments a variable, and compares the incremented value of the variable to a fixed number. If the variable is less than the fixed number, the program instructs a jump back to step two. Thus, a program loop is created which repeats steps two and three for the fixed number of times. After the fixed number of iterations has been completed, the second register stores a value which is the sum of the contents of the fixed number of addresses. In this type of program, each execution of step two after the first iteration requires the address generated in the previous iteration of step three. In one type of prior art computer system, each iteration of step two awaits execution of the previous iteration of step three and the program instructions are executed sequentially. The drawback of such a mode of operation is that each step in the loop adds to total execution time.
In other prior art computer systems, it was known to attempt to predict the address required by such an addition (or other type of AGI) step as being the address required by the previous iteration of the same step plus an offset or delta; the delta equals the difference between the two addresses required by the two previous iterations of the same program instruction. Then, the addition (or other type of AGI) step can begin before the address generation step is completed. This prediction technique works well when the addition (or other type of AGI step) always increments or decrements the previous address by a fixed delta. However, in many situations, the delta is not always fixed.
U.S. Pat. No. 5,093,777 discloses a more sophisticated technique for predicting addresses based on address patterns in a sequence of correct addresses.
AGIs can also occur in computing a target or subroutine address for a branch or jump instruction when the target address is generated by a previous instruction. A very successful prior art technique for predicting the target address is known as a Branch Target Buffer (BTB) technique. According to this technique, the address required for the present branch instruction is predicted to be the address used for the previous iteration of the same branch instruction. With the exception of subroutine returns and computed branches, which are a small fraction of all branches, the target is correct over 95% of the time.
In either of the foregoing prior art techniques, the actual address is calculated in parallel with the calculation of the predicted address and execution of the next instruction using the predicted address. When the actual address is finally calculated, it is compared to the predicted address. If the predicted address is correct, then processing continues where it left off using the predicted address. However, if the predicted address is incorrect, then any updates made using the predicted address are erased or overwritten, and this next instruction is executed again using the actual address. If the predictions are usually correct, system performance is improved.
A general object of the present invention is to provide an address prediction technique which is usually accurate.
Another general object of the present invention is to provide an effective address prediction technique which does not burden the system.